Along with the development of information technology, various hierarchical data can be found in a wide variety of database-related applications that are coming forth increasingly, including forums, mailing lists, business organization charts, content management categories, and product categories. Hierarchies, also known as tree structures, are collections of multiple data nodes where each node has a single parent, and zero or more child (with the exception of the root node, which has no parent).
Many methods have been proposed to visualize hierarchy data, such as listing, outline, tree diagram, cone tree, hyperbolic tree, treemap, or the like. Among them, treemap has turned into an important way to visualize hierarchy data.
Treemap was first designed by Brian Johnson and Ben Shneiderman during the 1990s. The concept of treemap is introduced in detail in the article “Tree-maps: A SpacFilling Approach to the Visualization of Hierarchical Information Structures” (Proc. IEEE Visualization '91, IEEE, Piscataway, N.J. (1991), 284-291) by Brian Johnson and Ben Shneiderman. Treemap is a way of space-constrained visualization of hierarchical data, and it uses size and color information to represent the attributes of leaf nodes. Treemap enables users to compare nodes and sub-trees at varying depth in the tree, thereby helping them recognize the complete structural information of the tree.
Treemap is highly effective in visualizing large hierarchical collections of quantitative data. A treemap divides the display region into a nested sequence of rectangles (corresponding regions of nodes) representing the hierarchy, wherein the areas of the rectangles correspond to some quantity (e.g. weight) in the hierarchical data set. FIG. 1 shows an example of a treemap.
A method for calculating the layout of the rectangles in treemap is very important to the application of treemap. Several treemap layout methods have been addressed. However, these existing treemap layout methods cannot achieve a perfect effect while handling a labeled treemap. Labeled treemap is different from a conventional treemap in that the rectangles corresponding to respective non-leaf nodes in the labeled treemap contain a part of spaces for their names and borders. By the labels, the new treemap makes it efficient for users to find the data they are interested in, which is a great improvement on the conventional treemap.
However, compared with a conventional treemap, the labeled treemap introduces a greater complexity into its construction process. In constructing a labeled treemap, since the labels and borders occupy the spaces that were originally belonging to corresponding nodes, and the existing treemap layout methods fail in determining the spaces required for the respective labels and borders before constructing, it is only possible that the regions of the nodes are firstly divided in the designated region, then the regions of the labels and borders are divided in the node regions, during the construction process. Thus, such case may arise: if the weights of two non-leaf nodes are equal, then two rectangles with the same area will be divided for the two nodes by the conventional method, herein it is assumed that the length and width of the two rectangles are selected in different coordinate directions, wherein the long side of one is along the x axis, while the short side of the other one is along the x axis. As the heights of labels are the same, the label in the former rectangle will occupy a larger region, so the remaining space for dividing to its child nodes will be smaller than that of the other rectangle. This will result in that not all the region sizes of the nodes are corresponding to the weights of the nodes in the constructed treemap, such that the treemap layout is not balanced. In the worst case, even such case may arise: at the end of the dividing for the constraint region by these existing treemap layout methods, there may be no more space to arrange the remaining leaf node with smaller weight, so that such leaf node is invisible in the constructed treemap.
Therefore, there is a need for a new method for constructing a labeled treemap with balanced layout, in order to solve such problems.